package com.cuz.daileetcode;

import com.cuz.daileetcode.utils.ListNode;
import com.cuz.daileetcode.utils.ListNodeUtils;
import jdk.nashorn.internal.ir.annotations.Ignore;

import java.time.Period;

/**
 * @author cuzz
 * @version 1.0
 * @description: 25. K 个一组翻转链表
 * 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
 * <p>
 * k 是一个正整数，它的值小于或等于链表的长度。
 * <p>
 * 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 * <p>
 * 进阶：
 * <p>
 * 你可以设计一个只使用常数额外空间的算法来解决此问题吗？
 * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：head = [1,2,3,4,5], k = 2
 * 输出：[2,1,4,3,5]
 * 示例 2：
 * <p>
 * <p>
 * 输入：head = [1,2,3,4,5], k = 3
 * 输出：[3,2,1,4,5]
 * 示例 3：
 * <p>
 * 输入：head = [1,2,3,4,5], k = 1
 * 输出：[1,2,3,4,5]
 * 示例 4：
 * <p>
 * 输入：head = [1], k = 1
 * 输出：[1]
 * 提示：
 * <p>
 * 列表中节点的数量在范围 sz 内
 * 1 <= sz <= 5000
 * 0 <= Node.val <= 1000
 * 1 <= k <= sz
 * @date 21:55 2021/9/28
 **/
public class Day11_2 {
    static class S1 {
        public static void main(String[] args) {
            ListNode listNode = ListNodeUtils.listGenerate(1, 2, 3, 4, 5,6,7);
            ListNode listNode1 = reverseKGroup(listNode, 2);
            ListNodeUtils.printList(listNode1);
        }
        public static ListNode reverseKGroup(ListNode head, int k) {
            if (k < 1) {
                return head;
            }
            ListNode newHead = null;
            ListNode cur = head;
            ListNode pre;
            ListNode preTemp;
            ListNode curTemp;
            ListNode preHead=head;
            boolean isFirst=true;
            while (true) {
                FlipHelp flipHelp = canContinueFlipOrNot(cur, k);
                if (flipHelp.tail==null){
                    break;
                }
                pre=flipHelp.tail;
                preTemp=pre.next;
                curTemp=cur;
                pre.next=null;
                ListNode listNode = reverseList(cur);
                preHead.next=listNode;
                if (isFirst){
                    newHead=listNode;
                    isFirst=false;
                }
                curTemp.next=preTemp;
                preHead=cur;
                cur=preTemp;
            }
            return newHead;
        }
        static class FlipHelp{
            boolean canFlipOrNot;
            ListNode tail;

            public FlipHelp(boolean canFlipOrNot, ListNode tail) {
                this.canFlipOrNot = canFlipOrNot;
                this.tail = tail;
            }
        }
        private static FlipHelp canContinueFlipOrNot(ListNode curHead, int k) {
            ListNode tail=curHead;
            boolean canFlip=true;
            for (int i = 0; i < k-1; i++) {
                if (tail == null) {
                    canFlip=false;
                    break;
                }
                tail = tail.next;
            }
            return new FlipHelp(canFlip,tail);
        }

        public static ListNode reverseList(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode cur = head;
            ListNode pre = head.next;
            boolean isFirst = true;
            while (pre != null) {
                ListNode temp = pre.next;
                pre.next = cur;
                if (isFirst) {
                    cur.next = null;
                    isFirst = false;
                }
                cur = pre;
                pre = temp;

            }
            return cur;
        }
    }
}
